/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-03-24
 * Time: 10:08
 */
public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        //1.创建dp表
        int n = matrix.length;
        int[][] dp = new int[n+1][n+2];
        //2.初始化
        for(int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        for(int j = 0; j < n+2; j++) {
            dp[0][j] = 0;
        }

        //3.状态转移
        //4.填表顺序
        for(int i = 1; i <=n; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i-1][j-1];
            }
        }

        //5.返回值
        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++) {
            ret = Math.min(dp[n][j],ret);
        }
        return ret;
    }
}
